package com.zp.self.module.level_4_算法练习.算法.双指针.左右指针;

/**
 * @author By ZengPeng
 */
public class 力扣_713_乘积小于K的子数组 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_713_乘积小于K的子数组().numSubarrayProductLessThanK(new int[]{10,5,2,6},100));
        System.out.println(new 力扣_713_乘积小于K的子数组().numSubarrayProductLessThanK(new int[]{1,1,1},1));
        System.out.println(new 力扣_713_乘积小于K的子数组().numSubarrayProductLessThanK(new int[]{2,1,1,1},2));
        System.out.println(new 力扣_713_乘积小于K的子数组().numSubarrayProductLessThanK(new int[]{57,44,92,28,66,60,37,33,52,38,29,76,8,75,22},18));
    }

    /**
    题目：给定一个正整数数组 nums和整数 k 。
     请找出该数组内乘积小于 k 的连续的子数组的个数。

     示例 1:
     输入: nums = [10,5,2,6], k = 100
     输出: 8
     解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
     需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

     示例 2:
     输入: nums = [1,2,3], k = 0
     输出: 0

    分析：【P 💕💞💝】
       1.双循环 : 需不需排序？连续还排鸡毛啊！  --O(n) 肯定慢，不实现了
       2.双指针 : 记录当前大小，不断乘以right向右移动
                  当累积>= k : 计算以i开头，会有多少钟情况:right - index;   将头尾除掉，下一个节点继续重新
                  优点：下一次开始：可以从前辈失败的位置继续啊
                      --执行用时：5 ms, 在所有 Java 提交中击败了31.25%的用户
        大佬：先找到大于的点，再移动左节点，剩下了每次复位的操作。right每多一个数，种类就多right-left+1 种
                      --执行用时：4 ms, 在所有 Java 提交中击败了99.97%的用户

    边界值 & 注意点：
       1. {1,1,1} 1   right==1 一直成立
     **/
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        //大佬：先找到大于的点，再移动左节点，剩下了每次复位的操作
        if(k==0){
            return 0;
        }
        int left=0,right=0;
        int ans = 0;
        int product = 1;
        while(right<nums.length){
            product = product * nums[right];
            while(product>=k && left <= right){
                product = product / nums[left];
                left++;
            }
            if(product < k)
                ans += (right-left+1);
            right++;
        }
        return ans;
        // 2.双指针 : 记录当前大小，不断乘以right向右移动
        /*if(k==0) return 0;
        int index=0,right=0,ji=1, sum =0;
        while (index<nums.length){
            //当right == nums.length  直接返回？
            if(right == nums.length){
                sum+=(right-index)*(right-index+1)/2;
                return sum;
            }
            //nums[right]>=k  ： index =right+1
            if(nums[right]>=k){
                sum+=(right-index)*(right-index+1)/2;
                ji=1;
                index=++right;
                continue;
            }
            while (right<nums.length){
                ji*=nums[right];
                if(ji>=k){
                    ji=ji/(nums[right]*nums[index]);
                    break;
                }
                right++;
            }
            sum+=right - index;
            index++;
        }
        return sum;*/
    }
}
